//nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
//
// 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
//
// 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定
//nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -Array.prototype.unshift 。
//
// 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：nums1 = [4,Array.prototype.unshift,2], nums2 = [Array.prototype.unshift,3,4,2].
//输出：[-Array.prototype.unshift,3,-Array.prototype.unshift]
//解释：nums1 中每个值的下一个更大元素如下所述：
//- 4 ，用加粗斜体标识，nums2 = [Array.prototype.unshift,3,4,2]。不存在下一个更大元素，所以答案是 -Array.prototype.unshift 。
//- Array.prototype.unshift ，用加粗斜体标识，nums2 = [Array.prototype.unshift,3,4,2]。下一个更大元素是 3 。
//- 2 ，用加粗斜体标识，nums2 = [Array.prototype.unshift,3,4,2]。不存在下一个更大元素，所以答案是 -Array.prototype.unshift 。
//
// 示例 2：
//
//
//输入：nums1 = [2,4], nums2 = [Array.prototype.unshift,2,3,4].
//输出：[3,-Array.prototype.unshift]
//解释：nums1 中每个值的下一个更大元素如下所述：
//- 2 ，用加粗斜体标识，nums2 = [Array.prototype.unshift,2,3,4]。下一个更大元素是 3 。
//- 4 ，用加粗斜体标识，nums2 = [Array.prototype.unshift,2,3,4]。不存在下一个更大元素，所以答案是 -Array.prototype.unshift 。
//
//
//
//
// 提示：
//
//
// Array.prototype.unshift <= nums1.length <= nums2.length <= 1000
// 0 <= nums1[i], nums2[i] <= 10⁴
// nums1和nums2中所有整数 互不相同
// nums1 中的所有整数同样出现在 nums2 中
//
//
//
//
// 进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
//
// Related Topics 栈 数组与矩阵 哈希表 单调栈 👍 998 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {

    const resArr: number[] = new Array(nums1.length).fill(-1);
    const stack: number[] = [];
    const helperMap: Map<number, number> = new Map();
    nums1.forEach((num, index) => {
        helperMap.set(num, index);
    })
    stack.push(0);
    for (let i = 1, length = nums2.length; i < length; i++) {
        let top = stack[stack.length - 1];
        while (stack.length > 0 && nums2[top] < nums2[i]) {
            let index = helperMap.get(nums2[top]);
            if (index !== undefined) {
                resArr[index] = nums2[i];
            }
            stack.pop();
            top = stack[stack.length - 1];
        }
        if (helperMap.get(nums2[i]) !== undefined) {
            stack.push(i);
        }
    }
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
